package 堆;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * 215. 数组中的第K个最大元素
 * 思路：如果要查找数组中的第K大个元素，则我们可以通过构建一个大顶堆的方式进行查找。
 *
 * 思路：
 * 方法一：堆（优先队列）
 * 维护一个大小为 K 的最小堆，遍历数组时保持堆中保存最大的 K 个元素。堆顶元素即为第 K 个最大元素。该方法的时间复杂度为 O(n log K)，空间复杂度为 O(K)。
 *
 * 方法二：快速选择算法
 * 基于快速排序的分区思想，每次选择一个随机 pivot，将数组划分为两部分，并根据 pivot 的位置与 K 的关系缩小搜索范围。平均时间复杂度为 O(n)，最坏情况为 O(n²)，但通过随机化可以优化实际表现。
 */
public class L_215 {

    // 使用堆排序 （维护一个容量为K大小的小顶堆，堆顶元素就是第K大个值）
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i : nums){
            minHeap.offer(i);
            if (minHeap.size() > k){
                minHeap.poll(); // 移除堆顶的最小元素
            }
        }
        return minHeap.peek(); // 堆顶元素即为第 K 大元素
    }


    /**
     * 快速排序来实现
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargestQuick(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        // 随机选择 pivot 并交换到右端
        Random rand = new Random();
        int pivotIndex = left + rand.nextInt(right - left + 1);
        swap(nums, pivotIndex, right);
        int pivot = nums[right];

        // 分区操作，将大于等于 pivot 的元素放到左侧
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] >= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right); // 将 pivot 放到最终位置

        int count = i - left + 1; // 左侧元素个数
        if (count == k) {
            return nums[i];
        } else if (count > k) {
            return quickSelect(nums, left, i - 1, k); // 在左侧继续找
        } else {
            return quickSelect(nums, i + 1, right, k - count); // 在右侧找第 k - count 大的元素
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
